#include "sort2.h"
void InsertSort(int* a, int n) {
	assert(a);
	int end = 0;
	for (int i = 0; i < n - 1; i++) {
		end = i;
		int x = a[end + 1];
		while (end >= 0) {
			if (x < a[end]) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				break;
			}
		}
		a[end + 1] = x;
	}
}
void printarr(int* a, int n)
{
	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1) {
		gap=gap/ 2;
		for (int i = 0; i < n - gap; ++i) {
			int end = i;
			int x = a[end + gap];
			while (end >= 0) {
				if (x < a[end]) {
					a[end + gap] = a[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = x;
		}
	}
}
void swap(int* a, int* b) {
	int tmp=*a;
	*a = *b;
	*b = tmp;
}
void SeletSort(int* a, int n) {
	int begini = 0;
	int endi = n - 1;	
	while (begini<endi) {
		int maxi = begini, mini = endi;
		for (int i = begini; i <= endi;i++) {
			if (a[i] < a[mini]) {
				mini = i;
			}
			if (a[i] > a[maxi]) {
				maxi = i;
			}                                         
		}
		swap(&a[mini], &a[begini]);
		if (begini == maxi) {
			maxi = mini;
		}
		swap(&a[maxi], &a[endi]);
		endi--;
		begini++;
	}
}
void adjustdown(int* a, int n, int parent) {
	int child = 2 * parent + 1;
	while (child < n) {
		if (child + 1 < n && a[child] < a[child + 1]) {
			child++;
		}
		if (a[child] > a[parent]) {
			swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
	}
}
void HeapSort(int* a, int n) {
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {             b               e   
		adjustdown(a, n, i);                              // 1 7 9 5 6 2 8 3 5
	}                                                        ma  m             

	int end = n - 1;
	while (end>0) {
		swap(&a[end], &a[0]);
		adjustdown(a, end, 0);
		end--;
	}
}



void SeletSort(int* a, int n) {
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end) {
		int maxi = begin;
		int mini = end;
		for (int i = begin; i <= end; ++i) {
			if (a[i] < a[mini]) {
				mini = i;
			}
			if (a[i] > a[maxi]) {
				maxi = i;
			}
		}
		swap(&a[begin], &a[mini]);                    
		if()
		swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}


void SeletSort(int* a, int n) {
	int begini = 0;
	int endi = n - 1;
	while (begini < endi) {
		int maxi = begini, mini = endi;
		for (int i = begini; i <= endi; i++) {
			if (a[i] < a[mini]) {
				mini = i;
			}
			if (a[i] > a[maxi]) {
				maxi = i;
			}
		}
		swap(&a[mini], &a[begini]);
		if (begin == maxi) {
			maxi = mini;
		}
		swap(&a[maxi], &a[end]);
		endi--;
		begini++;
	}
}

